Skip to main content

第44章 线性表和链表

线性表是计算机科学中最基础、最常用的数据结构之一，它是由n个具有相同特性的数据元素组成的有限序列。

44.1 线性表的基本概念​

44.1.1 定义​

线性表是由n(n≥0)n(n≥0)个数据元素(a1,a2,...,an)(a_1,a_2,...,a_n)组成的有限序列，其中：

  • nn为线性表的长度，n=0n=0时称为空表。
  • 数据元素可以是int、char等基础类型，也可以是结构体，所有元素类型必须统一。
  • 元素线性关系：除首元素无前驱、尾元素无后继外，其余元素有唯一直接前驱、唯一直接后继。

44.1.2 线性表基础操作​

  1. 初始化：创建空线性表
  2. 判空：判断长度是否为0
  3. 求长度：返回当前元素总数
  4. 获取指定下标元素
  5. 按值查找，返回位置（不存在返回-1）
  6. 指定位置插入元素
  7. 指定位置删除元素
  8. 清空所有元素

44.2 顺序表（数组实现的顺序存储）​

44.2.1 存储结构​

连续内存存放元素，同时记录当前长度、最大容量。

#define MAX_SIZE 100
typedef int ElemType;
typedef struct{
    ElemType data[MAX_SIZE];
    int length; // 当前有效元素个数
} SeqList;

44.2.2 核心操作实现​

初始化顺序表​

void initList(SeqList &L){
    L.length = 0;
}

插入元素（第i个位置插入，下标逻辑1开始）​

bool insertList(SeqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1) return false;
    if(L.length >= MAX_SIZE) return false;
    // 后移元素腾出位置
    for(int j = L.length; j >= i; j--){
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
    return true;
}

删除元素​

bool deleteList(SeqList &L, int i, ElemType &e){
    if(i < 1 || i > L.length) return false;
    e = L.data[i-1];
    // 元素前移覆盖
    for(int j = i; j < L.length; j++){
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}

按值查找​

int locateElem(SeqList L, ElemType e){
    for(int i = 0; i < L.length; i++){
        if(L.data[i] == e){
            return i + 1; // 返回1号位序
        }
    }
    return -1;
}

44.2.3 顺序表优缺点​

  • 优点：随机访问O(1)O(1)，存储无额外指针开销
  • 缺点：插入删除需要大量移动元素O(n)O(n)；容量固定易溢出/浪费内存

44.2.4 适用场景​

查询多、增删少，元素数量固定的场景。

44.3 链表（链式存储）​

链表不占用连续内存，依靠指针连接分散节点，每个节点包含数据域与指针域。

44.3.1 单链表​

每个节点仅存后继指针，带表头节点简化边界逻辑。

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

初始化空链表（头节点）​

void initList(LinkList &L){
    L = new LNode;
    L->next = nullptr;
}

头插法建表​

void createListHead(LinkList &L, int n){
    L = new LNode;
    L->next = nullptr;
    for(int i = 0; i < n; i++){
        LNode *p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

尾插法建表​

void createListTail(LinkList &L, int n) {
    L = new LNode;
    L->next = nullptr;
    LNode *r = L; // 尾指针
    for (int i = 0; i < n; i++){
        LNode *p = new LNode;
        cin >> p->data;
        p->next = nullptr;
        r->next = p;
        r = p;
    }
}

指定位置插入​

bool insertList(LinkList &L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    while (p != nullptr && j < i-1){
        p = p->next;
        j++;
    }
    if (p == nullptr) return false;
    LNode *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

指定位置删除​

bool deleteList(LinkList &L, int i, ElemType &e){
    LNode *p = L;
    int j = 0;
    while (p != nullptr && j < i-1){
        p = p->next;
        j++;
    }
    if (p == nullptr || p->next == nullptr) return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return true;
}

按值查找节点​

LNode* locateElem(LinkList L, ElemType e){
    LNode *p = L->next;
    while (p != nullptr && p->data != e){
        p = p->next;
    }
    return p;
}

44.3.2 双向链表​

节点同时存前驱、后继指针，可双向遍历

typedef struct DNode {
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
} DNode, *DLinkList;

特点：访问前驱O(1)O(1)；插入删除需要修改两个指针，代码更复杂。

44.3.3 循环单链表​

尾节点next指向头节点，形成环形结构；适合约瑟夫环等环形问题。

struct Node {
    int data;
    Node* next;
};

44.3.4 链表通用优缺点​

  • 优点：动态分配内存，插入删除仅改指针O(1)O(1)（找到前驱前提下）
  • 缺点：不支持随机访问，查找需遍历O(n)O(n)；每个节点额外存指针，内存开销更大

44.4 顺序表与链表对比​

特性顺序表单链表
内存分布连续分散
随机访问O(1)O(1)O(n)O(n)
中间增删O(n)O(n)O(1)O(1)（找到前驱）
内存开销仅存储数据数据+指针
扩容固定容量，需整体复制按需分配

44.5 三类链表对比​

类型节点指针尾节点指向访问前驱
单链表仅nextnullptrO(n)O(n)
双向链表prior+nextnullptrO(1)O(1)
循环单链表仅next头节点O(n)O(n)

44.6 线性表应用场景​

  1. 顺序表：数组、vector、需要频繁下标查询
  2. 单链表：任务队列、临时动态数据
  3. 双向链表：浏览器前进后退、LRU缓存
  4. 循环链表：约瑟夫问题、环形缓冲队列